package com.framework.collection.HashMap;

/**
 * @author duanzhizhou
 * @date 2025/3/31
 */
public class MyHashMap<K, V> {
    
    private Node<K, V>[] arr = new Node[16];
    
    private long cnt;
    
    public V put(K key, V value) {
        int idx=  hash(key);
        if (arr[idx] == null) {
            arr[idx] = new Node<>(key, value);
            ++cnt;
            resize();
            return null;
        } else {
            Node<K, V> cur = arr[idx];
            while (cur != null) {
                if (cur.key.equals(key)) {
                    V oldValue = cur.value;
                    cur.value = value;
                    return oldValue;
                }
                cur = cur.next;
            }
            Node<K, V> newNode = new Node<>(key, value);
            newNode.next = arr[idx];
            arr[idx] = newNode;
            ++cnt;
            resize();
        }
        return null;
    }
    
    public V remove (K key) {
        int idx = hash(key);
        if (arr[idx] == null) return null;
        if (arr[idx].key.equals(key)) {
            Node<K, V> node = arr[idx];
            arr[idx] = arr[idx].next;
            node.next = null;
            --cnt;
            return node.value;
        }
        Node<K, V> pre = arr[idx];
        Node<K, V> cur = arr[idx].next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                pre.next = cur.next;
                cur.next = null;
                --cnt;
                return cur.value;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return null;
    }
    
    public V get(K key) {
        int idx = hash(key);
        if (arr[idx] == null) return null;
        Node<K, V> cur = arr[idx];
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
    
    private int hash(K key) {
        return key.hashCode() & (arr.length - 1);
    }
    
    private void resize() {
        if (cnt > arr.length * 0.75) {
            @SuppressWarnings({"unchecked"})
            Node<K, V>[] newArr = (Node<K, V>[]) new Node[arr.length * 2];
            for (Node<K, V> node : arr) {
                if (node == null) continue;
                while (node != null) {
                    int newIdx = node.key.hashCode() & (newArr.length - 1);
                    Node<K, V> newNode = new Node<>(node.key, node.value);
                    if (newArr[newIdx] == null) {
                        newArr[newIdx] = newNode;
                    } else {
                        newNode.next = newArr[newIdx];
                        newArr[newIdx] = newNode;
                    }
                    node = node.next;
                }
            }
            arr = newArr;
            System.out.println("扩容到：" + arr.length);
        }
    }
    
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
